package BinaryTree;

import javax.swing.text.html.HTMLDocument;

public class Offer68lowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        // 这两个判断是冗余的
//        if(root==p){
//            return p;
//        }
//        if(root==q){
//            return q;
//        }

        if(root.val>p.val&&root.val>q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val<p.val&&root.val<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
//        都在左边去左边找, 都在右边去右边找
//        否则一左一右直接返回, roo=q/p也算这种情况,所以上面那两句判断是多余的
        return root;


        /*
        * 一般二叉树的最近公共祖先解法
        * */
//        if(root==null){
//            return root;
//        }
//        if(root==p || root==q){
//            return root;
//        }
//        TreeNode left=lowestCommonAncestor(root.left,p,q);
//        TreeNode right=lowestCommonAncestor(root.right,p,q);
//        if(left==null){
//            return right;
//        }
//        if(right==null){
//            return left;
//        }
//        return root;
    }
}
